package leetcode

import (
	"fmt"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// 假设nums1的长度小
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays(nums2, nums1)
	}
	low, hige, k, nums1Mid, nums2Mid := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0
	for low <= hige {
		// nums1:  .......... nums1[nums1Mid-1] | nums1[nums1Mid] ...........
		// nums2:  .......... nums2[nums2Mid-1] | nums2[nums2Mid] ...........
		nums1Mid = low + (hige-low)>>1
		nums2Mid = k - nums1Mid
		if nums1Mid > 0 && nums1[nums1Mid-1] > nums2[nums2Mid] { // nums1 中的分界线划多了，要向左边移动
			hige = nums1Mid - 1
		} else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid-1] { // nums1 中的分界线划少了，要向右边移动
			low = nums1Mid + 1
		} else {
			// 找到合适的划分了，需要输出最终结果了
			// 分为奇数偶数 2 种情况
			break
		}
	}
	fmt.Println(low, hige, k, nums1Mid, nums2Mid)
	midLeft, midRight := 0, 0
	if nums1Mid == 0 {
		midLeft = nums2[nums2Mid-1]
	} else if nums2Mid == 0 {
		midLeft = nums1[nums1Mid-1]
	} else {
		midLeft = max(nums1[nums1Mid-1], nums2[nums2Mid-1])
	}

	if (len(nums1)+len(nums2))&1 == 1 {
		return float64(midLeft)
	}

	if nums1Mid == len(nums1) {
		midRight = nums2[nums2Mid]
	} else if nums2Mid == len(nums2) {
		midRight = nums1[nums1Mid]
	} else {
		midRight = min(nums1[nums1Mid], nums2[nums2Mid])
	}
	return float64(midLeft+midRight) / 2
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func findMedianSortedArrays_fan(nums1 []int, nums2 []int) float64 {
	// 先将两个数组最大最小值相加/2.0
	// 这两个数组的长度为奇数还是偶数
	// 如果为奇数，
	nums1Z, nums2Z := 0.0, 0.0
	n1f, n2f := false, false
	if len(nums1)%2 == 1 {
		nums1Z = float64(nums1[len(nums1)/2])
	} else if len(nums1) == 0 {
		n1f = true
	} else {
		nums1Z = float64(nums1[len(nums1)/2-1]+nums1[len(nums1)/2]) / 2.0
	}

	if len(nums2)%2 == 1 {
		nums2Z = float64(nums2[len(nums2)/2])
	} else if len(nums2) == 0 {
		n2f = true
	} else {
		nums2Z = float64(nums2[len(nums2)/2-1]+nums2[len(nums2)/2]) / 2.0
	}
	if n1f {
		return nums2Z
	} else if n2f {
		return nums1Z
	} else {
		return (nums1Z + nums2Z) / 2.0
	}

}
